package wjl.leetcode.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 标签:树
 * 
 * @author ljw
 *
 */
public class TreePractice {
    public static void main( String[] args ) {
        boolean[][] arr = new boolean[2][3];
        System.out.println( arr[0][0] );
    }

    /* 路径总和Ⅱ : https://leetcode-cn.com/problems/path-sum-ii/  
     */
    public static List<List<Integer>> pathSumⅡ( TreeNode root, int sum ) {
        List<List<Integer>> list     = new ArrayList<>();
        List<Integer>       pathList = new ArrayList<>();
        loopTree( root, sum, list, pathList );
        return list;
    }

    public static void loopTree( TreeNode root, int sum, List<List<Integer>> list,
            List<Integer> pathList ) {
        if ( root == null ){
            return;
        }
        List<Integer> subList = new ArrayList<>( pathList );
        subList.add( root.val );
        sum -= root.val;
        if ( root.left == null && root.right == null && sum == 0 ){
            list.add( subList );
        }
        loopTree( root.left, sum, list, subList );
        loopTree( root.right, sum, list, subList );
    }

    /*
     * 迷路的机器人:https://leetcode-cn.com/problems/robot-in-a-grid-lcci/
     */
    public List<List<Integer>> pathWithObstacles( int[][] obstacleGrid ) {
        List<List<Integer>> pathList = new ArrayList<>();
        int                 ysize    = obstacleGrid[0].length;
        int                 xsize    = obstacleGrid.length;
        if ( ysize == 0 || xsize == 0 ){
            return pathList;
        }
        int         x       = 0;
        int         y       = 0;
        boolean[][] visited = new boolean[xsize][ysize];
        doWork( obstacleGrid, xsize, ysize, x, y, visited, pathList );
        return pathList;
    }

    public boolean doWork( int[][] obstacleGrid, int xsize, int ysize, int x, int y,
            boolean[][] visited, List<List<Integer>> pathList ) {
        if ( x >= xsize || y >= ysize || obstacleGrid[x][y] == 1 || visited[x][y] ){
            return false;
        }
        visited[x][y] = true;
        pathList.add( Arrays.asList( x, y ) );
        if ( x == xsize - 1 && y == ysize - 1 ){
            return true;
        }
        if ( doWork( obstacleGrid, xsize, ysize, x + 1, y, visited, pathList )
                || doWork( obstacleGrid, xsize, ysize, x, y + 1, visited, pathList ) ){
            return true;
        }
        pathList.remove( pathList.size() - 1 );
        return false;
    }


}
